/**
 此法超时
 * @param {number[][]} matrix
 * @return {number}
 */
export var longestIncreasingPath = function (matrix) {
  const [m, n] = [matrix.length, matrix[0].length]
  const dirt = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]

  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
  // const visited = new Array(m).fill(0).map(() => new Array(n).fill(false))
  let ans = 1

  const dfs = function (i, j) {
    if (dp[i][j] > 0) return dp[i][j]
    let isNoNext = false
    let long = 1
    for (const [offestI, offestJ] of dirt) {
      const nextI = i + offestI
      const nextJ = j + offestJ
      if (nextI < 0 || nextI >= m || nextJ < 0 || nextJ >= n) continue
      if (matrix[nextI][nextJ] <= matrix[i][j]) continue
      long = Math.max(long, dfs(nextI, nextJ) + 1)
      ans = Math.max(ans, long)
    }
    if (isNoNext) {
      dp[i][j] = 1
      return 1
    }
    dp[i][j] = Math.max(dp[i][j], long)
    return long
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      dfs(i, j, 1, i, j)
    }
  }
  // console.log(dp)

  return ans
}
